package 数组中只出现一次的数字;


import java.util.*;

//题目描述
//一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution
{
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[])
    {
        //判断输入
        if (array.length<4)
        {
            num1[0]=0;
            num2[0]=0;
        }

        //方法一，双重循环，相等不做处理，不等就输出，时间复杂度n2
        //方法二，排序后，找不重复的，nlogn+n
        //方法三，hash方法
        //方法四，异或方法，任何一个数异或它自己都是0，不同的位才为1
        //求全部的异或值，得到的就是num1和num2的异或值
        //那其异或值一定不为0，去其中为1的一位进行分类，该为为0的是一组，为1的是一组，两组分别异或，得到的
        //分别是num1和num2
        int xor=0;
        for (int i = 0; i < array.length; i++)
        {
            xor^=array[i];

        }
        int index=1;
        while ((xor&index)==0)
            index=index<<1;
        //分类
        int result1=0;
        int result2=0;
        for (int i = 0; i < array.length; i++)
        {
            if ((array[i]&index)==0)
                result1=result1^array[i];
            else
                result2=result2^array[i];

        }
        num1[0]=result1;
        num2[0]=result2;

    }

    public void FindNumsAppearOnce1(int [] array,int num1[] , int num2[]) {
        //哈希算法
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i < array.length; i++){
            if(map.containsKey(array[i]))
                map.put(array[i],2);
            else
                map.put(array[i],1);
        }
        int count = 0;
        for(int i=0; i < array.length; i++){
            if(map.get(array[i]) == 1){
                if(count == 0){
                    num1[0] =  array[i];
                    count++;
                }else
                    num2[0] =  array[i];
            }
        }

    }
    public static void main(String[] args)
    {
        Solution solution = new Solution();
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        int[] array = {2, 4, 6, 4, 6, 7};
        solution.FindNumsAppearOnce(array,num1,num2);
        System.out.println(num1[0]);
        System.out.println(num2[0]);

    }
}
